import java.util.*;

/**
 * Created by zhourh on 2018/8/13.
 * 编写一个算法来判断一个数是不是“快乐数”。

 一个“快乐数”定义为：对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和，然后重复这个过程直到这个数变为 1，也可能是无限循环但始终变不到 1。如果可以变为 1，那么这个数就是快乐数。

 示例:

 输入: 19
 输出: true
 解释:
 12 + 92 = 82
 82 + 22 = 68
 62 + 82 = 100
 12 + 02 + 02 = 1
 */
public class HappyNumber {

    public static void main(String[] args) {
        System.out.print(new HappyNumber().isHappy(19));
    }

    private static Set<Integer> unHappyNums = new HashSet<>();
    private static Set<Integer> happyNums = new HashSet<>();

    static {
        happyNums.add(1);
    }

    public boolean isHappy(int n) {
        if (happyNums.contains(n)) {
            return true;
        }
        if (unHappyNums.contains(n)) {
            return false;
        }

        Set<Integer> paths = new HashSet<>();
        paths.add(n);

        int next = nextNum(n);
        while (next != 1 && !happyNums.contains(next) && !unHappyNums.contains(next) && !paths.contains(next)) {
            paths.add(next);
            next = nextNum(next);
        }

        if (next == 1 || happyNums.contains(next)) {
            happyNums.addAll(paths);
            return true;
        }

        unHappyNums.addAll(paths);
        return false;
    }

    private int nextNum(int n) {
        List<Integer> bits = new ArrayList<>();
        while (n > 0) {
            bits.add(n % 10);
            n /= 10;
        }

        int next = 0;
        for (int bit : bits) {
            next += bit * bit;
        }

        return next;
    }
}
